﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace StudyOne
{
	public class SeqList<T> : IListDS<T>
	{
		//顺序表的容量
		private int _maxSize;
		//数组，用于存储顺序表中的数据元素
		private T[] data;
		//指示顺序表中最后一个元素的位置
		private int _last;

		//索引器
		public T this[int index]
		{
			get { return data[index]; }
			set { data[index] = value; }
		}

		/// <summary>
		/// 最后一个元素位置的属性
		/// </summary>
		public int Last
		{
			get { return _last; }
			set { _last = value; }
		}

		/// <summary>
		/// 容器的属性
		/// </summary>
		public int MaxSize
		{
			get { return _maxSize; }
			set { _maxSize = value; }
		}

		/// <summary>
		/// 构造函数
		/// </summary>
		/// <param name="size"></param>
		public SeqList(int size)
		{
			data = new T[size];
			_maxSize = size;
			_last = -1;
		}

		//求长度
		public int GetLength()
		{
			return _last + 1;
		}

		//清空顺序表
		public void Clear()
		{
			_last = -1;
		}

		//判断线性表是否为空
		public bool IsEmpty()
		{
			if (_last == -1)
			{
				return true;
			}
			else
			{
				return false;
			}
		}

		//判断线性表是否为满
		public bool IsFull()
		{
			if (_last == _maxSize - 1)
			{
				return true;
			}
			else
			{
				return false;
			}
		}

		//在顺序表的末尾添加新元素
		public void Append(T item)
		{
			if (IsFull())
			{
				Console.WriteLine("线性表已满！");
				return;
			}
			data[++_last] = item;
		}

		//插入操作
		public void Insert(T item, int i)
		{
			//判断线性表是否已满
			if (IsFull())
			{
				Console.WriteLine("线性表已满！");
				return;
			}

			//判断插入的位置是否正确，i小于1表示在第1个位置之前插入，i>last+2表示在最后一个元素后面的第二个位置插入
			if (i < 1 || i > _last + 2)
			{
				Console.WriteLine("索引异常！");
				return;
			}

			//在线性表的表尾插入数据元素
			if (i == _last + 2)
			{
				data[_last + 1] = item;
			}
				//在表的其他位置插入数据元素
			else
			{
				//元素移动
				for (int j = _last; j >= i - 1; --j)
				{
					data[j + 1] = data[j];
				}
				//将新的元素插入到第i个位置上
				data[i - 1] = item;
			}
			++_last;
		}

		//删除操作
		public T Delete(int i)
		{
			T tmp = default(T);
			if (IsFull())
			{
				Console.WriteLine("线性表已满！");
				return tmp;
			}

			//判断线性表是否为空
			if (IsEmpty())
			{
				Console.WriteLine("线性表为空！");
				return tmp;
			}

			//判断插入的位置是否正确，i小于1表示在第1个位置之前插入，i>last+2表示在最后一个元素后面的第二个位置插入
			if (i < 1 || i > _last + 2)
			{
				Console.WriteLine("索引异常！");
				return tmp;
			}

			//删除最后一个元素
			if (i == _last + 1)
			{
				tmp = data[_last--];
			}
				//删除的不是最后一个元素
			else
			{
				//元素移动
				tmp = data[i - 1];
				for (int j = i; j <= _last; ++j)
				{
					data[j] = data[j + 1];
				}
			}
			//修改表长
			--_last;
			return tmp;
		}

		//取表元
		public T GetItem(int i)
		{
			if (IsEmpty() || (i < 0) || (i > _last + 1))
			{
				Console.WriteLine("线性表为空或者索引异常");
				return default(T);
			}

			return data[i];
		}

		//按值查找
		public int Locate(T value)
		{
			if (IsEmpty())
			{
				Console.WriteLine("线性表为空！");
				return -1;
			}
			//循环处理顺序表
			int i = 0;
			for (; i <= _last; ++i)
			{
				if (value.Equals(data[i]))
				{
					break;
				}
			}
			//顺序表中不存在与给定值相等的元素
			if (i > _last)
			{
				return -1;
			}
			return i;
		}

		//顺序倒置
		public void Reverse()
		{
			T tmp = default(T);
			int len = GetLength() - 1;
			for (int i = 0; i <= len/2; i++)
			{
				tmp = data[i];
				data[i] = data[len - i];
				data[len - i] = tmp;
			}
		}
	}
}
